import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
import java.util.Stack;

public class Select {

/*
稳定：如果a原本在b前面，而a=b，排序后a仍在b前面
不稳定：如果a原本在b前面，而a=b，排序后a可能会出现在b后面
内排序：所有排序都是在内存中完成的
外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行
时间复杂度：一个算法执行所耗费的时间
空间复杂度：运行完一个程序所需内存的大小
冒泡排序 选择排序 插入排序
希尔排序 归并排序 快速排序 堆排序
计数排序 桶排序 基数排序
*/
    static int len;
    public static void main(String[] args) {
    }




    /**
     * 1.选择排序O(n2) 不稳定
     */
    public static int[] selectionSort(int[] arr){
        for (int i = 0; i < arr.length-1; i++) {
            int min = i;
            for (int j = i+1; j < arr.length; j++) {
                if (arr[j] < arr[min]){
                    min = j;
                }
            }
            int temp = arr[min];
            arr[min] = arr[i];
            arr[i] = temp;

        }
        return arr;
    }
    /**
     * 2.冒泡排序O(n2) 稳定
     */
    public static int[] bubbleSort(int[] arr){
        if (arr.length==0)
            return arr;
        int temp = 0;
        for (int i = 0; i < arr.length-1; i++) {
            for (int j = i + 1;j < arr.length;j++){
                if (arr[i] > arr[j]){
                    temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        return arr;
    }
    /**
     * 3.插入排序On2 稳定
     */
    public static int[] insertionSort(int[] arr){
        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j > 0 ; j--) {
                if (arr[j]<arr[j-1]){
                    int temp = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = temp;
                }
            }
        }
        return arr;
    }
    /**
     * 4.快速排序:O(NlogN) 稳定
     */
    public static int[] quickSort(int[] arr,int low ,int high){

        int z,y;
        int i = low;
        int j = high;
        if (low>high)
            return arr;
        int temp = arr[low];
        while(i<j){
            while(temp<=arr[j]&&i<j){
                j--;
            }
            while (temp>=arr[i]&&i<j){
                i++;
            }
            if (i<j){
               z = arr[i];
               y = arr[j];
               arr[i] = y;
               arr[j] = z;
            }
        }
        arr[low] = arr[i];
        arr[i] = temp;
        quickSort(arr,low,i-1);
        quickSort(arr,i+1,high);


        return arr;
    }

    /**
     * 5.希尔排序：O(NlogN) 不稳定
     * 是将相隔某个“增量”的记录组成一个子序列，实现跳跃式移动，使得排序的效率提高。需要注意的是，增量序列的最后一个增量值必须等于1才行。
     * 在此我们选择增量gap=length/2，缩小增量继续以gap = gap/2的方式，这种增量选择我们可以用一个序列来表示，{n/2,(n/2)/2...1}，称为增量序列。
     * 希尔排序的增量序列的选择与证明是个数学难题，我们选择的这个增量序列是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。
     *
     */
    public static int[] shellSort(int[] arr){
        int len = arr.length;
        int gap = len/2;
        int temp;
        while(gap>0){
            for (int i = gap; i < len; i++) {
                temp = arr[i];
                int preIndex = i - gap;
                while(preIndex >= 0&&arr[preIndex]>temp){
                    arr[preIndex + gap] = arr[preIndex];
                    preIndex -= gap;
                }
                arr[preIndex + gap] = temp;
            }
            gap /= 2;
        }
        return arr;
    }
    /**
     * 6.堆排序
     * 堆是一个近似完全二叉树的结构，并同时满足堆积的性质：子节点的键值或索引总是小于或大于它的父节点。
     * 一个堆在程序中可以简单的用数组描述，那么堆排序算法可以分为两步：1.将无序数组构造成一个最大堆。2.对该最大堆进行排序
     * 堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，
     *                  此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，
     *                  便能得到一个有序序列了
     * 分别找到i元素的左孩子和右孩子，若左孩子与右孩子中有比i元素大的，找到最大的那个元素，并且与i元素交换位子，
     * 然后对交换位子的那个最大元素再次调用MaxHeap方法。
     * 注意，此算法成立的条件是i元素的左子树与右子树都是最大堆!!!
     */
    //声明全局变量，用于记录数组array的长度
    /**
     * 堆排序算法
     *
     * @param array
     * @return
     */
    public static int[] HeapSort(int[] array) {
        len = array.length;
        if (len < 1) return array;
        //1.构建一个最大堆
        buildMaxHeap(array);
        //2.循环将堆首位（最大值）与末位交换，然后在重新调整最大堆
        while (len > 0) {
            swap(array, 0, len - 1);
            len--;
            adjustHeap(array, 0);
        }
        return array;
    }
    /**
     * 建立最大堆
     *
     * @param array
     */
    public static void buildMaxHeap(int[] array) {
        //从最后一个非叶子节点开始向上构造最大堆
        for (int i = (len/2 - 1); i >= 0; i--) { //感谢 @让我发会呆 网友的提醒，此处应该为 i = (len/2 - 1)
            adjustHeap(array, i);
        }
    }
    /**
     * 调整使之成为最大堆
     *
     * @param array
     * @param i
     */
    public static void adjustHeap(int[] array, int i) {
        int maxIndex = i;
        //如果有左子树，且左子树大于父节点，则将最大指针指向左子树
        if (i * 2 < len && array[i * 2] > array[maxIndex])
            maxIndex = i * 2;
        //如果有右子树，且右子树大于父节点，则将最大指针指向右子树
        if (i * 2 + 1 < len && array[i * 2 + 1] > array[maxIndex])
            maxIndex = i * 2 + 1;
        //如果父节点不是最大值，则将父节点与最大值交换，并且递归调整与父节点交换的位置。
        if (maxIndex != i) {
            swap(array, maxIndex, i);
            adjustHeap(array, maxIndex);
        }
    }
    public static int[] swap(int[] arr,int a,int b){
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
        return arr;
    }

    /**
     * 7归并排序（O(nlogn)）需要额外的空间 稳定
     */
    public static int[] MergeSort(int[] array){
        if (array.length < 2)
            return array;
        int mid = array.length / 2;
        int[] left = Arrays.copyOfRange(array, 0, mid);
        int[] right = Arrays.copyOfRange(array, mid, array.length);
        return merge(MergeSort(left), MergeSort(right));
    }
    /**
     * 归并排序——将两段排序好的数组结合成一个排序数组
     */
    public static int[] merge(int[] left, int[] right){
        int[] result = new int[left.length + right.length];
        for (int index = 0, i = 0, j = 0; index < result.length; index++){
            if (i >= left.length)
                result[index] = right[j++];
            else if (j >= right.length)
                result[index] = left[i++];
            else if (left[i] > right[j])
                result[index] = right[j++];
            else
                result[index] = left[i++];
        }
        return result;
    }
    /**
     * 8计数排序稳定
     * 借用一个额外空间c(长度为（max-min+1）)来存储每个数字出现的次数
     */
    public static int[] countingSort(int[] arr){
        int max=arr[0],min=arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i]>max)
                max = arr[i];
            if (arr[i] < min)
                min = arr[i];
        }
        int[] bucket = new int[max-min+1];
        Arrays.fill(bucket,0);
        for (int i = 0; i < arr.length; i++) {
            bucket[arr[i]-min]++;
        }
        int index = 0,i = 0;
        while (index < arr.length){
            if (bucket[i]!=0){
                arr[index] = i;
                bucket[i]--;
                index++;
            }else i++;
        }
        return arr;
    }
    /**
     * 9.桶排序是计数排序的升级版，稳定，最快，以空间换时间
     * 人为设置一个BucketSize，作为每个桶所能放置多少个不同数值（例如当BucketSize==5时，该桶可以存放｛1,2,3,4,5｝这几种数字，
     但是容量不限，即可以存放100个3）；
     遍历输入数据，并且把数据一个一个放到对应的桶里去；
     对每个不是空的桶进行排序，可以使用其它排序方法，也可以递归使用桶排序；
     从不是空的桶里把排好序的数据拼接起来。
     */
    /**
     * 桶排序
     */
    public static ArrayList<Integer> BucketSort(ArrayList<Integer> array, int bucketSize) {
        if (array == null || array.size() < 2)
            return array;
        int max = array.get(0), min = array.get(0);
        // 找到最大值最小值
        for (int i = 0; i < array.size(); i++) {
            if (array.get(i) > max)
                max = array.get(i);
            if (array.get(i) < min)
                min = array.get(i);
        }
        //一共需要几个桶
        int bucketCount = (max - min) / bucketSize + 1;

        ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketCount);
        ArrayList<Integer> resultArr = new ArrayList<>();
        //添加桶
        for (int i = 0; i < bucketCount; i++) {
            bucketArr.add(new ArrayList<Integer>());
        }
        //添加某个桶里面的多个数字（在这个桶区间的数字）
        for (int i = 0; i < array.size(); i++) {
            bucketArr.get((array.get(i) - min) / bucketSize).add(array.get(i));
        }
        for (int i = 0; i < bucketCount; i++) {
            if (bucketSize == 1) { // 如果带排序数组中有重复数字时
                for (int j = 0; j < bucketArr.get(i).size(); j++)
                    resultArr.add(bucketArr.get(i).get(j));
            } else {
                if (bucketCount == 1)
                    bucketSize--;
                ArrayList<Integer> temp = BucketSort(bucketArr.get(i), bucketSize);
                for (int j = 0; j < temp.size(); j++)
                    resultArr.add(temp.get(j));
            }
        }
        return resultArr;
    }
    /**
     * 基数排序
     */
    public static int[] radixSort(int[] arr){
        //1.先算出最大数的位数
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            max = Math.max(max, arr[i]);
        }
        int maxDigit = 0;
        while(max!=0){
            max/=10;
            maxDigit++;
        }
        int mod = 10,div = 1;
        ArrayList<ArrayList<Integer>> bucketList = new ArrayList<ArrayList<Integer>>();
        //桶的个数
        for (int i = 0; i < 10; i++)
            bucketList.add(new ArrayList<Integer>());
        //最大数是几位进行几次大循环
        for (int i = 0; i < maxDigit; i++, mod *= 10, div *= 10) {
            for (int j = 0; j < arr.length; j++) {
                int num = (arr[j] % mod) / div;
                //把数组元素存储到某个数字的桶里
                bucketList.get(num).add(arr[j]);
            }
            int index = 0;
            for (int j = 0; j < bucketList.size(); j++) {
                for (int k = 0; k < bucketList.get(j).size(); k++)
                    arr[index++] = bucketList.get(j).get(k);
                bucketList.get(j).clear();
            }
        }
        return arr;
    }



}
